package dmsxl.dongtaiguihua;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2023/7/28 16:46
 */
public class dtgh13_416 {

    public static void main(String[] args) {
//        int[] nums = {1, 5, 11, 5};
        int[] nums = {1, 2, 3, 5};
        System.out.println(canPartition(nums));
    }

//    自己写的，逻辑错误，不正确
    public static boolean canPartition1(int[] nums) {
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < nums.length - 1; i++){
            int countl = 0;
            int countr = 0;
            for (int l = 0; l <= i; l++){
                countl += nums[l];
            }
            for (int r = i + 1; r < nums.length; r++){
                countr += nums[r];
            }
            System.out.println(countl);
            System.out.println(countr);
            if (countl == countr)
                return true;
        }
        return false;
    }

//    答案
    public static boolean canPartition2(int[] nums) {
        int target = 0;
        for (int i = 0; i < nums.length; i++){
            target += nums[i];
        }
        if (target % 2 != 0) return false;
        target /= 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++){
            for (int j = target; j >= nums[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[target] == target;
    }

    //    答案
    public static boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) return false;
        int n = nums.length;
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        //总和为奇数，不能平分
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        int[] dp = new int[target + 1];
        System.out.println(dp.length);
        System.out.println(target);
        for(int i = 0; i < n; i++) {
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其价值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}
